package com.example.leetcode.c601_c700.c643;
/**
 * 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
 *
 *  
 *
 * 示例：
 *
 * 输入：[1,12,-5,-6,50,3], k = 4
 * 输出：12.75
 * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
 *  
 *
 * 提示：
 *
 * 1 <= k <= n <= 30,000。
 * 所给数据范围 [-10,000，10,000]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-average-subarray-i
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 子数组最大平均数 I
 * @author zhanpengguo
 * @date 2021-02-04 8:09
 */
public class Solution {

    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int maxSum = 0;
        for (int i = 0; i < k; i++) {
            maxSum += nums[i];
        }
        int sum = maxSum;
        for (int i = k; i < n; i++) {
            sum = sum + nums[i] - nums[i - k];
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
        return (double) maxSum / k;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,12,-5,-6,50,3};
        double v = solution.findMaxAverage(nums, 6);
        System.out.println(v);
    }
}
